/*
 *  Min Priority Queue
 *
 *  Promotion tips:
 *  1. from fixed to resizable
 */

package algs4.sort;

import java.util.Random;

public class MinPQ<Key extends Comparable<Key>>
{
    private int n;
    private Key[] pq;

    /*-------- Constructors --------*/
    public MinPQ(int capacity) {
        n  = 0;
        pq = (Key[]) new Comparable[capacity+1];
    }

    /*-------- Public methods --------*/
    public void insert(Key v) {
        pq[++n] = v;
        swim(n);
    }

    public Key min() {
        return pq[1];
    }

    public Key delMin() {
        Key v = pq[1];
        pq[1] = pq[n--];
        pq[n+1] = null;
        sink(1);

        return v;
    }

    public int size() {
        return n;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    /*-------- Private methods --------*/
    private void swim(int k) {
        Key v = pq[k];
        while (k > 1 && v.compareTo(pq[k/2]) < 0) {
            pq[k] = pq[k/2];
            k /= 2;
        }
        pq[k] = v;
    }

    private void sink(int k) {
        int i;
        Key v = pq[k];

        while ((i = k * 2) <= n) {
            if (i < n && pq[i].compareTo(pq[i+1]) > 0) i++;
            if (v.compareTo(pq[i]) <= 0)               break;
            pq[k] = pq[i];
            k = i;
        }
        pq[k] = v;
    }

    private static void show(Comparable[] a) {
        for (Comparable i : a)
            System.out.print(i + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.out.println("Usage: Command N");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);;

        // Build random array of integer
        Integer[] a          = new Integer[n];
        Random random        = new Random(System.currentTimeMillis());
        MinPQ<Integer> minpq = new MinPQ<>(5 + 1);
        for (int i = 0; i < n; i++) {
            a[i] = random.nextInt(n);
            minpq.insert(a[i]);

            if (minpq.size() > 5) minpq.delMin();
        }

        System.out.print("DATA: "); show(a);
        System.out.print("TOP5: ");
        while (!minpq.isEmpty())
            System.out.print(minpq.delMin() + " ");
        System.out.println();
    }
}
